class Solution:
    def kthSmallest(self, matrix, k: int) -> int:
        n = len(matrix)

        def check(mid):
            i,j = n-1,0
            num = 0
            while 0<=i<n and 0<=j<n:
                if matrix[i][j]>mid:
                    i-=1
                else:
                    num += i + 1
                    j+=1
            return num>=k
        left = matrix[0][0]
        right = matrix[-1][-1]
        while left<right:
            mid = (left + right) //2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

if __name__ == '__main__':
    so = Solution()
    matrix = [[1,2],[1,3]]
    k = 3
    r = so.kthSmallest(matrix, k)
    print(r)
